package com.排序数组中相同数字出现的个数;

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int first= foundFirst(array,k,0,array.length-1);
        int last = foundLast(array,k,0,array.length-1);
        System.out.println(first);
        System.out.println(last);
        if(first!=-1&&last!=-1)
            return last-first+1;
        else 
            return 0;
    }
    public int foundFirst(int []array,int k,int start,int end){
        int mid=(start+end)/2;
        int index=-1;
        while(start<=end){
            if(array[mid]==k){
                if(start==mid||array[mid-1]!=k){
                 index=mid;
                 return index;
                 }
                else{
                    end=mid-1;
                }
            }
            else if(array[mid]>k)
                end=mid-1;
            else
                start=mid+1;
            mid=(start+end)/2;
        }
        return index;
    }
    public int foundLast(int []array,int k,int start,int end){
        int mid=(start+end)/2;
        int index=-1;
        while(start<=end){
            if(array[mid]==k){
                if(end==mid||array[mid+1]!=k){
                index=mid;
                return index;
                }
                else{
                    start=mid+1;
                }
            }
            else if(array[mid]>k)
                end=mid-1;
            else
                start=mid+1;
            mid=(start+end)/2;
        }
        return index;
    }
}
